package leetcode.LinkedList;

/**
 * head-->node1->node2->node3->node4
 * <p>
 * 1: cur->node1 1->null
 *
 * @author MaoLin Wang
 * @date 2020/2/1113:22
 */
public class _206ReverseList {
    /**
     * 不带头的迭代
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;


    }

    /**
     * 递归方式
     */
    public static ListNode reverseRecursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        return recursion(null, head);
    }

    private static ListNode recursion(ListNode newNode, ListNode head) {
        if (head!=null){
            ListNode next = head.next;
            head.next=newNode;
            newNode=head;
            return recursion(newNode,next);
        }
        return newNode;
    }

    /**
     * 带头的迭代
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode newNode = new ListNode(0);

        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = newNode.next;
            newNode.next = cur;
            cur = curNext;
        }
        head = newNode.next;
        return head;
    }
    public  static ListNode reverseList3(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode result=new ListNode(0);
        ListNode temp=head;
        while (temp!=null){
            ListNode next=temp.next;
            temp.next=result.next;
            result.next=temp;
            temp=next;
        }
        return result.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        l1.next.next.next.next = new ListNode(5);
        ListNode node = reverseList3(l1);
        ListNode.printNode(node);
    }
}
